package org.nowcoder.leetcode.DP;

/**
 * Title  : 509. Fibonacci Number
 * Source : https://leetcode.cn/problems/fibonacci-number/
 * Author : XrazYang
 * Date   : 2023-12-26
 */

public class LeetCode_509 {
    public int fib(int n) {
        //递归
        // if (n < 2) return n;
        // return fib(n - 1) + fib(n - 2);

        //动态规划
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
